public class _44 {
    static class Solution1 {
        public boolean isMatch(String s, String p) {
            boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
            dp[0][0] = true;
            //递推关系
            // if p[j] == '*'
            // dp[i+1][j+1] = dp[i][j] || dp[i+1][j] || dp[i][j+1]
            // if p[j] == '?' || p[j] == s[i]:
            // dp[i+1][j+1] = dp[i][j];
            //填充边
            for (int j = 0; j < p.length(); j++) {
                if (p.charAt(j) == '*') dp[0][j + 1] = true;
                else break;
            }
            for (int i = 0; i < s.length(); i++) {
                for (int j = 0; j < p.length(); j++) {
                    char si = s.charAt(i);
                    char pj = p.charAt(j);
                    if (pj == '?' || si == pj) {
                        dp[i + 1][j + 1] = dp[i][j];
                    }
                    if (pj == '*') {
                        dp[i + 1][j + 1] = dp[i][j] || dp[i + 1][j] || dp[i][j + 1];
                    }
                }
            }
            return dp[s.length()][p.length()];
        }
    }
    static class Solution2 {
        public boolean isMatch(String s, String p) {
            return dfs(new Boolean[s.length()][p.length()], s.toCharArray(), p.toCharArray(), 0, 0);
        }
        private boolean dfs(Boolean[][] dp, char[] s, char[] p, int i, int j) {
            if (i == s.length && j == p.length) return true;
            if (i > s.length || (i < s.length && j == p.length)) return false;
            if (i < s.length) {
                if (dp[i][j] != null) return dp[i][j];
                if (p[j] == '?' || p[j] == s[i]) {
                    return dp[i][j] = dfs(dp, s, p, i + 1, j + 1);
                }
            }
            boolean res = false;
            if (p[j] == '*') {
                res = dfs(dp, s, p, i + 1, j + 1) || dfs(dp, s, p, i + 1, j) || dfs(dp, s, p, i, j + 1);
            }
            if (i < s.length) dp[i][j] = res;
            return res;
        }
    }
}
